﻿#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<algorithm>
#include<vector>
#include<iostream>
#include<set>
#include<cmath>
#include<unordered_set>
#include<unordered_map>

using namespace std;

//一、双指针算法

//1.移动零 https://leetcode.cn/problems/move-zeroes/description/
void moveZeroes(vector<int>& nums);

//2.复写零 https://leetcode.cn/problems/duplicate-zeros/description/
void duplicateZeros(vector<int>& arr);

//3.快乐数 https://leetcode.cn/problems/happy-number/description/
bool isHappy(int n);

//4.盛水最多的容器 https://leetcode.cn/problems/container-with-most-water/description/
int maxArea(vector<int>& height);

//5.有效的三角形个数 https://leetcode.cn/problems/valid-triangle-number/description/
int triangleNumber(vector<int>& nums);

//6.查找总价为目标值的两个商品 https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/
vector<int> twoSum(vector<int>& price, int target);

//7.三数之和 https://leetcode.cn/problems/3sum/description/
vector<vector<int>> threeSum(vector<int>& nums);

//8.四数之和 https://leetcode.cn/problems/4sum/description/
vector<vector<int>> fourSum(vector<int>& nums, int target);



//二、滑动窗口算法

//9.长度最小的子数组 https://leetcode.cn/problems/minimum-size-subarray-sum/description/
int minSubArrayLen(int target, vector<int>& nums);

//10.无重复字符的最长子串 https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
int lengthOfLongestSubstring(string s);

//11.最大连续1的个数 https://leetcode.cn/problems/max-consecutive-ones-iii/description/
int longestOnes(vector<int>& nums, int k);

//12.将X减小到0的最小操作数 https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/
int minOperations(vector<int>& nums, int x);

//13.水果成篮 https://leetcode.cn/problems/fruit-into-baskets/description/
int totalFruit(vector<int>& fruits);

//14.找到字符串中所有字母异位词 https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/
vector<int> findAnagrams(string s, string p);

//15.串联所有单词的子串 https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/
vector<int> findSubstring(string s, vector<string>& words);

//16.最小覆盖子串 https://leetcode.cn/problems/minimum-window-substring/description/
string minWindow(string s, string t);



//三、二分查找算法

//17.二分查找 https://leetcode.cn/problems/binary-search/description/
int search(vector<int>& nums, int target);

//18.在排序数组中查找元素的第一个和最后一个位置 
//https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/
vector<int> searchRange(vector<int>& nums, int target);

//19.搜索插入位置 https://leetcode.cn/problems/search-insert-position/description/
int searchInsert(vector<int>& nums, int target);

//20.x 的平方根 https://leetcode.cn/problems/sqrtx/description/
int mySqrt(int x);

//21.山脉数组的峰顶索引 https://leetcode.cn/problems/peak-index-in-a-mountain-array/description/
int peakIndexInMountainArray(vector<int>& arr);

//22.寻找峰值 https://leetcode.cn/problems/find-peak-element/description/
int findPeakElement(vector<int>& nums);

//23.寻找旋转排序数组中的最小值 https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/description/
int findMin(vector<int>& nums);

//24.点名 https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/
int takeAttendance(vector<int>& records);



//四、前缀和算法

//25.【模板】前缀和 https://www.nowcoder.com/practice/acead2f4c28c401889915da98ecdc6bf?tpId=230&tqId=2021480&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196
class solution_getSum;

//26.【模板】二维前缀和 https://www.nowcoder.com/practice/99eb8040d116414ea3296467ce81cbbc?tpId=230&tqId=2023819&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196
class solution_two_dimension_sum;

//27.寻找数组的中心下标 https://leetcode.cn/problems/find-pivot-index/description/
int pivotIndex(vector<int>& nums);

//28.除自身以外数组的乘积 https://leetcode.cn/problems/product-of-array-except-self/description/
vector<int> productExceptSelf(vector<int>& nums);

//29.和为 K 的子数组 https://leetcode.cn/problems/subarray-sum-equals-k/description/
int subarraySum(vector<int>& nums, int k);

//30.和可被 K 整除的子数组 https://leetcode.cn/problems/subarray-sums-divisible-by-k/description/
int subarraysDivByK(vector<int>& nums, int k);

//31.连续数组 https://leetcode.cn/problems/contiguous-array/description/
int findMaxLength(vector<int>& nums);

//32.矩阵区域和 https://leetcode.cn/problems/matrix-block-sum/description/
vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k);



//五、位运算

//33.判定字符是否唯一 https://leetcode.cn/problems/is-unique-lcci/description/
bool isUnique(string astr);

//34.丢失的数字 https://leetcode.cn/problems/missing-number/description/
int missingNumber(vector<int>& nums);

//35.两整数之和 https://leetcode.cn/problems/sum-of-two-integers/description/
int getSum(int a, int b);

//36.只出现一次的数字 II https://leetcode.cn/problems/single-number-ii/description/
int singleNumber(vector<int>& nums);

//37.消失的两个数字 https://leetcode.cn/problems/missing-two-lcci/description/
vector<int> missingTwo(vector<int>& nums);



//六、模拟

//38.替换所有的问号 https://leetcode.cn/problems/replace-all-s-to-avoid-consecutive-repeating-characters/description/
string modifyString(string s);

//39.提莫攻击 https://leetcode.cn/problems/teemo-attacking/description/
int findPoisonedDuration(vector<int>& timeSeries, int duration);

//40.Z 字形变换 https://leetcode.cn/problems/zigzag-conversion/description/
string convert(string s, int numRows);

//41.外观数列 https://leetcode.cn/problems/count-and-say/description/
string countAndSay(int n);

//42.数青蛙 https://leetcode.cn/problems/minimum-number-of-frogs-croaking/description/
int minNumberOfFrogs(string croakOfFrogs);



//七、分治 - 快速排序

//43.颜色分类 https://leetcode.cn/problems/sort-colors/description/
void sortColors(vector<int>& nums);

//44.排序数组 https://leetcode.cn/problems/sort-an-array/description/
class sortArray_Solution;

//45.数组中的第K个最大元素 https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
